import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;


public class Dijkstra {
	public Graph grafo;
	public PriorityQueue<Etiqueta> cola;
	
	public Dijkstra(){//Graph grafo){
		//this.grafo = grafo;
		grafo = new Graph();
		/**
		grafo.addEdge(new Vertice(0, "a"), new Vertice(16, "b"));
		grafo.addEdge(new Vertice(0, "a"), new Vertice(10, "c"));
		grafo.addEdge(new Vertice(0, "a"), new Vertice(5, "d"));
		grafo.addEdge(new Vertice(0, "b"), new Vertice(16, "a"));
		grafo.addEdge(new Vertice(0, "b"), new Vertice(2, "c"));
		grafo.addEdge(new Vertice(0, "b"), new Vertice(4, "f"));
		grafo.addEdge(new Vertice(0, "b"), new Vertice(6, "g"));
		grafo.addEdge(new Vertice(0, "c"), new Vertice(10, "a"));
		grafo.addEdge(new Vertice(0, "c"), new Vertice(2, "b"));
		grafo.addEdge(new Vertice(0, "c"), new Vertice(12, "f"));
		grafo.addEdge(new Vertice(0, "c"), new Vertice(20, "e"));
		grafo.addEdge(new Vertice(0, "c"), new Vertice(4, "d"));
		grafo.addEdge(new Vertice(0, "d"), new Vertice(5, "a"));
		grafo.addEdge(new Vertice(0, "d"), new Vertice(4, "c"));
		grafo.addEdge(new Vertice(0, "d"), new Vertice(15, "e"));
		grafo.addEdge(new Vertice(0, "e"), new Vertice(10, "d"));
		grafo.addEdge(new Vertice(0, "e"), new Vertice(10, "c"));
		grafo.addEdge(new Vertice(0, "e"), new Vertice(3, "f"));
		grafo.addEdge(new Vertice(0, "e"), new Vertice(5, "z"));
		grafo.addEdge(new Vertice(0, "f"), new Vertice(12, "c"));
		grafo.addEdge(new Vertice(0, "f"), new Vertice(4, "b"));
		grafo.addEdge(new Vertice(0, "f"), new Vertice(8, "g"));
		grafo.addEdge(new Vertice(0, "f"), new Vertice(16, "z"));
		grafo.addEdge(new Vertice(0, "f"), new Vertice(3, "e"));
		grafo.addEdge(new Vertice(0, "g"), new Vertice(6, "b"));
		grafo.addEdge(new Vertice(0, "g"), new Vertice(8, "f"));
		grafo.addEdge(new Vertice(0, "g"), new Vertice(7, "z"));
		grafo.addEdge(new Vertice(0, "z"), new Vertice(7, "g"));
		grafo.addEdge(new Vertice(0, "z"), new Vertice(16, "f"));
		grafo.addEdge(new Vertice(0, "z"), new Vertice(5, "e"));
		*/
		cola = new PriorityQueue();
	}
	
	public void setGrafo(Graph grafo){
		this.grafo = grafo;
	}
	
	public ArrayList<String> calcular(Vertice inicio){
		ArrayList<String> vCamino = new ArrayList<String>();
		ArrayList<Integer> pCamino = new ArrayList<Integer>();
		ArrayList<Vertice> vert = new ArrayList<Vertice>();
		vert.addAll(grafo.adjacencyMap.keySet());
		ArrayList<Etiqueta> etiq = new ArrayList<Etiqueta>();
		
		for (int i = 0; i < grafo.size(); i++){
			String tempValor = ((Vertice) vert.get(i)).getValor();
			etiq.add(new Etiqueta(Integer.MAX_VALUE, tempValor));
		}
		vCamino.add(inicio.getValor());
		pCamino.add(inicio.getPeso());
		Etiqueta inic = new Etiqueta(0, inicio.getValor());
		cola.add(inic);
		
		for(Etiqueta i : etiq)
			if (i != inic)
				cola.add(i);
		
		while(vCamino.size() != grafo.size()){
			System.out.println(":S");
			for (Vertice i : (LinkedList<Vertice>) grafo.adjacencyMap.get(inicio))
				if (! vCamino.contains(i.getValor())){
					cola.add(new Etiqueta(i.getPeso() + pCamino.get(vCamino.indexOf(inicio.getValor())), i.getValor()));
				}
			Etiqueta temp = cola.remove();
			inicio = new Vertice(0, temp.getValor());
			if (!vCamino.contains(temp.getValor())){
				vCamino.add(temp.getValor());
				pCamino.add(temp.getPeso());
			}
		}
		for (String i : vCamino)
			System.out.println(i);
		for (Integer i : pCamino)
			System.out.println(i);
		return vCamino;
	}
}
